/**
 * 
 */
package com.dalonedrow.module.hq.graph;

import com.dalonedrow.engine.graph.Graph;
import com.dalonedrow.engine.graph.GraphEdge;
import com.dalonedrow.engine.graph.TwoDMapGraphNode;
import com.dalonedrow.engine.graph.WeightedGraphEdge;
import com.dalonedrow.engine.sprite.base.SimpleVector2;

/**
 * @author DaLoneDrau
 */
public final class HQCellGraph implements Graph {
	/** the one and only instance of the <code>HQCellGraph</code> class. */
	private static HQCellGraph	instance;
	/** flag indicating a node has an invalid index. */
	public static final int		INVALID_NODE_INDEX	= -1;
	/**
	 * Gives access to the singleton instance of {@link HQCellGraph}.
	 * @return {@link HQCellGraph}
	 */
	public static HQCellGraph getInstance() {
		if (HQCellGraph.instance == null) {
			HQCellGraph.instance = new HQCellGraph();
		}
		return HQCellGraph.instance;
	}
	/** the list of edges in the graph. */
	private WeightedGraphEdge[]	edges;
	/** the list of nodes or vertices in the graph. */
	private TwoDMapGraphNode[]	nodes;
	/** Hidden constructor. */
	private HQCellGraph() {
		nodes = new TwoDMapGraphNode[0];
		edges = new WeightedGraphEdge[0];
	}
	/**
	 * Adds an edge to the graph.
	 * @param edge the {@link GraphEdge} being added
	 */
	public void addEdge(final WeightedGraphEdge edge) {
		// does this edge already exist?
		int index = -1;
		for (int i = 0; i < edges.length; i++) {
			if (edges[i] != null
					&& edges[i].equalsDirected(edge.getFrom(), edge.getTo())) {
				index = i;
				break;
			}
		}
		if (index == -1) {
			// add to edges
			index = getNextFreeEdgeIndex();
			if (index == -1) {
				index = edges.length;
				extendEdgesArray();
			}
			edges[index] = edge;
		}
	}
	/**
	 * Adds a node to the graph and returns the index it was assigned to.
	 * @param x the x-coordinate of the node being added
	 * @param y the y-coordinate of the node being added
	 * @return <code>int</code>
	 * @throws Exception if an error occurs
	 */
	public int addNode(final float x, final float y) throws Exception {
		int index = -1;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].getIndex() >= 0
					&& nodes[i].equals(x, y)) {
				index = i;
				break;
			}
		}
		if (index == -1) {
			index = getNextFreeNodeIndex();
			if (index == -1) {
				index = nodes.length;
				extendNodesArray();
			}
			TwoDMapGraphNode node =
					new TwoDMapGraphNode(index, (int) x, (int) y);
			nodes[index] = node;
		}
		return index;
	}
	/**
	 * Adds a node to the graph and returns the index it was assigned to.
	 * @param v the {@link SimpleVector2} representing the node being added
	 * @return <code>int</code>
	 * @throws Exception if an error occurs
	 */
	public int addNode(final SimpleVector2 v) throws Exception {
		return addNode((float) v.getX(), (float) v.getY());
	}
	/**
	 * Adds a node to the graph and returns the index it was assigned to.
	 * @param node the {@link TwoDMapGraphNode} being added
	 * @return <code>int</code>
	 */
	public int addNode(final TwoDMapGraphNode node) {
		int index = -1;
		if (node.getIndex() > -1) {
			index = node.getIndex();
			if (node.getIndex() >= nodes.length) {
				// extend the array
				extendNodesArray(node.getIndex() + 1);
			}
		} else {
			index = getNextFreeNodeIndex();
			if (index == -1) {
				index = nodes.length;
				extendNodesArray();
			}
		}
		nodes[index] = node;
		return index;
	}
	/** Clears the graph. */
	public void clear() {
		for (int i = 0; i < nodes.length; i++) {
			nodes[i].setIndex(-1);
		}
		for (int i = 0; i < edges.length; i++) {
			edges[i].setFrom(-1);
			edges[i].setTo(-1);
		}
	}
	/** Extends the edges array by 1. */
	private void extendEdgesArray() {
		this.extendEdgesArray(edges.length + 1);
	}
	/**
	 * Extends the edges array by a specific length.
	 * @param newLength the new length
	 */
	private void extendEdgesArray(final int newLength) {
		WeightedGraphEdge[] dest = new WeightedGraphEdge[newLength];
		System.arraycopy(edges, 0, dest, 0, edges.length);
		// fill the remaining slot with empty nodes
		for (int i = edges.length; i < dest.length; i++) {
			dest[i] = null;
		}
		edges = dest;
		dest = null;
	}
	/** Extends the nodes array by 1. */
	private void extendNodesArray() {
		this.extendNodesArray(nodes.length + 1);
	}
	/**
	 * Extends the nodes array by a specific length.
	 * @param newLength the new length
	 */
	private void extendNodesArray(final int newLength) {
		TwoDMapGraphNode[] dest = new TwoDMapGraphNode[newLength];
		System.arraycopy(nodes, 0, dest, 0, nodes.length);
		// fill the remaining slot with empty nodes
		for (int i = nodes.length; i < dest.length; i++) {
			dest[i] = new TwoDMapGraphNode();
		}
		nodes = dest;
		dest = null;
	}
	/**
	 * Gets an edge at a specific index.
	 * @param index the index.
	 * @return {@link GraphEdge}
	 * @throws Exception if an error occurs
	 */
	public WeightedGraphEdge getEdge(final int index) throws Exception {
		return edges[index];
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public WeightedGraphEdge[] getEdgesFromNode(final int index)
			throws Exception {
		boolean found = false;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].getIndex() == index) {
				found = true;
				break;
			}
		}
		if (!found) {
			throw new Exception("Node " + index
					+ " was never added to the graph.");
		}
		WeightedGraphEdge[] list = new WeightedGraphEdge[0];
		for (int i = 0; i < edges.length; i++) {
			if (edges[i].getFrom() == index) {
				WeightedGraphEdge[] dest =
						new WeightedGraphEdge[list.length + 1];
				System.arraycopy(list, 0, dest, 0, list.length);
				dest[list.length] = edges[i];
				list = dest;
				dest = null;
			}
		}
		return list;
	}
	/**
	 * Gets the index of the next free edge index in the array. If no index is
	 * available, -1 is returned.
	 * @return <code>int</code>
	 */
	private int getNextFreeEdgeIndex() {
		int index = -1;
		for (int i = 0; i < edges.length; i++) {
			if (edges[i] == null) {
				index = i;
				break;
			}
		}
		return index;
	}
	/**
	 * Gets the index of the next free node index in the array.
	 * @return <code>int</code>
	 */
	public int getNextFreeNodeIndex() {
		int index = -1;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].getIndex() == -1) {
				index = i;
				break;
			}
		}
		return index;
	}
	/**
	 * Gets the node that represents a specific set of coordinates.
	 * @param x the node's x-coordinate
	 * @param y the node's y-coordinate
	 * @return {@link TwoDMapGraphNode}
	 * @throws Exception if an error occurs
	 */
	public TwoDMapGraphNode getNode(final double x, final double y)
			throws Exception {
		return getNode((float) x, (float) y);
	}
	/**
	 * Gets the node that represents a specific set of coordinates.
	 * @param x the node's x-coordinate
	 * @param y the node's y-coordinate
	 * @return {@link TwoDMapGraphNode}
	 * @throws Exception if an error occurs
	 */
	public TwoDMapGraphNode getNode(final float x, final float y)
			throws Exception {
		int index = -1;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].getIndex() >= 0
					&& nodes[i].equals(x, y)) {
				index = i;
				break;
			}
		}
		return nodes[index];
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public TwoDMapGraphNode getNode(final int index) {
		TwoDMapGraphNode node = null;
		if (index < nodes.length) {
			node = nodes[index];
		}
		return node;
	}
	/**
	 * Gets the total number of active nodes present in the graph.
	 * @return <code>int</code>
	 */
	public int getNumActiveNodes() {
		int num = 0;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] != null
					&& nodes[i].getIndex() >= 0) {
				num++;
			}
		}
		return num;
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public int getNumberOfNodes() {
		int num = 0;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] != null) {
				num++;
			}
		}
		return num;
	}
	/**
	 * Gets the number of edges present in the graph.
	 * @return <code>int</code>
	 */
	public int getNumEdges() {
		int num = 0;
		for (int i = 0; i < edges.length; i++) {
			if (edges[i] != null) {
				num++;
			}
		}
		return num;
	}
	/**
	 * Determines if the graph is empty.
	 * @return true if the graph contains no nodes; false otherwise.
	 */
	public boolean isEmpty() {
		return getNumberOfNodes() > 0;
	}
	/**
	 * Determines if a node with the given index is present in the graph.
	 * @param index the index
	 * @return true if the node is present has a valid index; false otherwise
	 */
	public boolean isPresent(final int index) {
		boolean b = false;
		if (nodes.length > index
				&& nodes[index].getIndex() >= 0) {
			b = true;
		}
		return b;
	}
	/**
	 * Removes an edge from the graph.
	 * @param from the node the edge was coming from
	 * @param to the node the edge leads to
	 */
	public void removeEdge(final int from, final int to) {
		for (int i = 0; i < edges.length; i++) {
			if (edges[i] != null
					&& edges[i].equalsDirected(from, to)) {
				edges[i] = null;
			}
		}
	}
	/**
	 * Removes an edge from the graph, regardless of the direction. If there
	 * were two edges in the map connecting the same nodes, but in opposite
	 * directions, both would be removed.
	 * @param from the node the edge was coming from
	 * @param to the node the edge leads to
	 */
	public void removeEdgeInBothDirections(final int from, final int to) {
		for (int i = 0; i < edges.length; i++) {
			if (edges[i] != null
					&& edges[i].equalsUndirected(from, to)) {
				edges[i] = null;
			}
		}
	}
	/**
	 * Removes a node at a specific index from the graph.
	 * @param index the index
	 */
	public void removeNode(final int index) {
		nodes[index].setIndex(-1);
	}
}
